home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6768 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.6 KB
  1. Path: news.microsoft.com!news
  2. From: a-cnadc@microsoft.com (Dann Corbit)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Finding a prime number
  5. Date: 15 Feb 1996 00:28:47 GMT
  6. Organization: Microsoft Corporation
  7. Message-ID: <4ftunv$vc0@news.microsoft.com>
  8. References: <4e875s$nqk@reader2.ix.netcom.com> <7c8_9601301722@tor250.org> <4f7n1o$ol9@mother.usf.edu> <4fl2tl$ln6@ns2.emirates.net.ae> <4fnnfuINNib7@keats.ugrad.cs.ubc.ca> <4fp2kt$pks@oban.cc.ic.ac.uk>
  9. NNTP-Posting-Host: 157.57.171.202
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.93.14
  12.  
  13. In article <4fp2kt$pks@oban.cc.ic.ac.uk>, a.kruczkowski@ic.ac.uk says...
  14. >
  15. >I haven't seen the origins of this thread, so excuse me if it's not
  16. >relevant.
  17. >
  18. >I found a way to calculate primes fairly quickly (well, I was using ARM
  19. >code then but the algorithm may be worth something).
  20. >
  21. >It works more on patterns within the Sieve of Erastothanes (sp?) rather than
  22. >the numbers themselves.  Whilst working it out by hand on paper, I got
  23. >to the stage where I decided that 1, 2, 3 and all multiples of 2 could be
  24. >discarded.  I then saw that beyond this, all primes numbers were a subset
  25. >of 6n+1 and 6n-1.  So I crated a new list of numbers going 5, 7, 11, 13...
  26. >From these numbers, I marked the prime ones.  A pattern emerged.  I don't
  27. >know what it was, since it was a long time ago, but there is something
  28. >there!  Anyhow, the method I used to do the calculation was to create a
  29. >data block in memory which was a series of 0s (I used bytes but use
  30. >whatever!) and then stepped through the block using the pattern to mark
  31. >255s (or whatever) where I had manually circled numbers on my piece of
  32. >paper.
  33. >
  34. >The trick was that whilst the data block was consecutive, the first
  35. >item represented 5, the second 7, the third 11 and so on.
  36. >This was not needed at execution time since only the algortihm was
  37. >being timed.  After it had run its course, the data was gone through
  38. >again doing nothing more than checking for 0 "I am not prime" or
  39. >255 "I am prime".
  40. >
  41. >Any comments or am I way off here? ;-)
  42.  
  43. I have something like this.  I have a 16 megabyte bit list, where
  44. all of the prime bits are 0 and the non-prime bits are 1.
  45. I also stored only the odd bits, since even bits are not prime,
  46. except for 2.  Hence, I can tell immediately if a number between
  47. 1 and 32,000,000*8 = 256,000,000 is prime.  This method is not
  48. useful for numbers bigger than 256 million.  In comp.sci.math
  49. there is a discussion of a new method for finding prime numbers that
  50. I have invented for those who are interested in that sort of thing.
  51. -- 
  52. The opinions expressed in this message are my own personal views 
  53. and do not reflect the official views of Microsoft Corporation.
  54.  
  55.